import java.util.*;

public class Sort {
    public static void main(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        mergeSortNor(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println();
        System.out.println();
        //双端队列
        Deque<Integer> deque1 = new LinkedList<>();//用双向链表实现
        Deque<Integer> deque2 = new ArrayDeque<>();//用循环数组实现
    }

    private static void mergeSortNor(int[] arr) {
        int[] tmp = new int[arr.length];
        int gap = 1;
        //[i , i + gap - 1] [i + gap , i + 2 * gap - 1]
        while (gap < arr.length) {
            for (int i = 0; i < arr.length; i += 2 * gap) {
                int begin1 = i;
                int end1 = i + gap - 1;
                int begin2 = i + gap;
                int end2 = i + 2 * gap - 1;

                int pos = i;

                //没有右边区间
                if (begin2 >= arr.length) {
                    break;
                }

                //右边越界
                if (end2 >= arr.length) {
                    end2 = arr.length - 1;
                }

                while (begin1 <= end1 && begin2 <= end2) {
                    if (arr[begin1] < arr[begin2]) {
                        tmp[pos++] = arr[begin1++];
                    } else {
                        tmp[pos++] = arr[begin2++];
                    }
                }

                while (begin1 <= end1) {
                    tmp[pos++] = arr[begin1++];
                }
                while (begin2 <= end2) {
                    tmp[pos++] = arr[begin2++];
                }

                for (int j = i; j <= end2; j++) {
                    arr[j] = tmp[j];
                }
            }

            gap *= 2;
        }
    }

    public static void main6(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr) {
        int[] tmp = new int[arr.length];
        merge_Sort(arr, tmp, 0, arr.length - 1);
    }

    private static void merge_Sort(int[] arr, int[] tmp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >>> 1;

        merge_Sort(arr, tmp, left, mid);
        merge_Sort(arr, tmp, mid + 1, right);
        int begin1 = left;
        int begin2 = mid + 1;
        int end1 = mid;
        int end2 = right;
        int pos = begin1;
        while (begin1 <= end1 && begin2 <= end2) {
            if (arr[begin1] < arr[begin2]) {
                tmp[pos++] = arr[begin1++];
            } else {
                tmp[pos++] = arr[begin2++];
            }
        }

        while (begin1 <= end1) {
            tmp[pos++] = arr[begin1++];
        }
        while (begin2 <= end2) {
            tmp[pos++]  = arr[begin2++];
        }

        for (int i = left; i <= right; i++) {
            arr[i] = tmp[i];
        }

    }

    public static void main5(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        quickSortNor(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSortNor(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(arr.length - 1);
        while (!stack.isEmpty()) {
            //左右指针法
            int end = stack.pop();
            int begin = stack.pop();
            int key = begin;
            int left = begin;
            int right = end;
            while (begin < end) {
                while (begin < end && arr[end] >= arr[key]) {
                    end--;
                }
                while (begin < end && arr[begin] <= arr[key]) {
                    begin++;
                }
                swap(arr, end, begin);
            }
            swap(arr, begin, key);
            if (left < begin) {
                stack.push(key);
                stack.push(begin - 1);
            }
            if (begin < right) {
                stack.push(begin + 1);
                stack.push(right);
            }

        }

    }

    public static void quickSortFront(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }

        int prev = left;
        int cur = prev + 1;
        int key = arr[left];
        while (cur <= right) {
            if (arr[cur] <= key) {
                prev++;
            }
            if (arr[prev] >= arr[cur]) {
                swap(arr, prev, cur);
            }
            cur++;
        }
        swap(arr, prev, left);

        //[left, prev - 1] prev [prev + 1, right]
        quickSortFront(arr, left, prev - 1);
        quickSortFront(arr, prev + 1, right);
    }
    public static void main4(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        quickSortFront(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void main3(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] arr, int left, int right) {
        //挖坑法
        if (left > right) {
            return ;
        }

        int pivot = left;
        int begin = left;
        int end = right;
        int key = arr[left];

        while (begin < end) {
            //从后向前开始找
            while (arr[end] >= key && begin < end) {
                end--;
            }
            //找到了交换
            arr[pivot] = arr[end];
            pivot = end;
            while (arr[begin] <= key && begin < end) {
                begin++;
            }
            arr[pivot] = arr[begin];
            pivot = begin;
        }

        pivot = begin;
        arr[pivot] = key;
        //[left, pivot - 1] pivot [pivot + 1, right]
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);

    }
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            int j = i + 1;
            for ( ; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }

    public  static void swap(int[] arr,int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void main2(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        Sort.selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void main1(String[] args) {
        int[] arr = {1,5,9,33,4,0,-4,-5,0};
        ShellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void ShellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            for (int i = 0; i < arr.length - gap; i++) {
                int end = i;
                int tmp = arr[end + gap];
                while (end >= 0) {
                    if (arr[end] > tmp) {
                        arr[end + gap] = arr[end];
                        end -= gap;
                    } else {
                        break;
                    }
                }
                arr[end + gap] = tmp;
            }
        }
    }
}
